package com.south.base.test.arithmetic;

import java.util.Arrays;
import java.util.TreeMap;

/**
 * 第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
 * 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
 * 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
 *
 * @author Administrator
 * @date 2019/5/17 10:00
 */
public class LimitCapacityOfShip {
    public static int numRescueBoats(int[] people, int limit) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i : people) {
            map.merge(i, 1, Integer::sum);
        }
        int count = 0;

        for (int i : people) {
            if (map.get(i) == null) {
                continue;
            }
            count++;
            int b = limit - i;
            map.merge(i, 1, (o, s) -> o - s);
            if (map.get(i) == 0) {
                map.remove(i);
            }
            if (map.size() == 0) {
                continue;
            }
            int key = map.firstKey();
            if (key > b) {
                continue;
            }
            key = map.floorKey(b);

            if (key > b) {
                continue;
            }
            if (map.get(key) != 0) {
                map.merge(key, 1, (o, s) -> o - s);
                if (map.get(key) == 0) {
                    map.remove(key);
                }
            }
        }
        return count;
    }

    public static int numRescueBoats2(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        int num = 0;
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
                right--;
                num++;
            } else {
                right--;
                num++;
            }
        }
        return num;
    }

    public static void main(String[] args) {
        int count = numRescueBoats(new int[]{3, 2, 2, 1}, 3);
        System.out.println(count);
    }
}
